package 数据结构练习;

//单源最短路径
public class 迪杰斯特拉算法 {
    public static void main(String[] args) {
        int n = 0;
        int[][] map = new int[6][6];
        int[][] b = new int[][]{
                {0,1,6},{0,3,5},
                {1,2,5},{2,3,7},
                {0,2,1},{1,4,3},
                {3,5,2},{2,4,5},
                {2,5,4},{4,5,6}
        };
        //初始化地图
        for(int j=0;j<map.length;j++){
            for(int k=0;k<map.length;k++){
                if(j != k){
                    map[j][k] = 99999999;
                }
            }
        }
        for(int[] x : b){
            map[x[0]][x[1]] = x[2];
            map[x[1]][x[0]] = x[2];
        }
        int dis[][] = dijkstra(map,n);
        for(int i=0;i<dis.length;i++){
            System.out.println(n+"->"+i+" : "+dis[i][0]);
        }
    }

    public static int[][] dijkstra(int[][] map,int n){
        int[][] dis = new int[map.length][2];
        int[] min = new int[]{99999999,-1};
        int count = 1;
        int k = n;
        //初始化dis数组
        for(int i=0;i<dis.length;i++){
            dis[i][0] = 999999999;
        }
        dis[n][1] = 1;
        while (count<map.length){
            //扫描第k行 改变数值
            for(int i=0;i<map.length;i++){
                if(map[n][k]+map[k][i]<dis[i][0] && dis[i][1]==0){
                    dis[i][0] = map[n][k]+map[k][i];
                }
            }
            //扫描dis表，求最小值确定
            for(int i=0;i<dis.length;i++){
                if(dis[i][0]<min[0] && dis[i][1]==0){
                    min[0] = dis[i][0];
                    min[1] = i;
                }
            }
            //确定最小值
            dis[min[1]][1] = 1;
            k = min[1];
            min = new int[]{99999999,-1};
            //计数器加一
            count++;
        }
        return dis;
    }
}
